A computer system is a layered device that includes a hardware layer, a firmware and operating system layer, and an applications program layer. The hardware layer of the computer system is often referred to as a physical (hardware) platform. The platform may include processors, chipsets, communications, memory, boards and systems. Typically, a single operating system controls all hardware layer resources in the computer system.
The computer system's physical resources may be virtualized to allow multiple operating systems to run on a single physical platform. A virtualized system may include a virtual machine monitor that arbitrates access to the physical platform's resources so that multiple operating systems can share them. The virtual machine monitor presents to each operating system, a set of platform interfaces that constitute a virtual machine. Thus, one computer system (hardware platform) can function as multiple “virtual” machines (platforms).
The physical platform may include a network processor, that is, a programmable device that is optimized for processing packets at high speed. Typically, the network processor classifies a received packet using a tuple of a set of fields from headers included in the packet. For example, the tuple of a set of fields may include a Transport Control Protocol (TCP) source port field, TCP destination port field, Internet Protocol (IP) source address field and IP destination address field. Using this tuple of a set of fields as a key, a database storing policy entries (policy table or policy database) may be queried to identify a configured policy that dictates how to handle the packet.
The policy entries in the policy database are typically stored as linked lists or as linear arrays. In order to improve searching performance, a lookup mechanism is typically implemented. One implementation of a lookup mechanism is a Recursive Flow Classification (RFC) algorithm which is discussed at http://klamath.stanford.edu/˜pankaj/thesis/chapter4.pdf.
One limitation of the RFC algorithm is that lookup efficiency decreases exponentially as the number of policy entries in the database increases. Another limitation is that each time the database is updated an RFC table associated with the database needs to be re-generated. The regeneration process can be quite slow, with the time taken to generate an RFC table from a database being directly proportional to the number of policy entries in the database.
Although the following Detailed Description will proceed with reference being made to illustrative embodiments of the claimed subject matter, many alternatives, modifications, and variations thereof will be apparent to those skilled in the art. Accordingly, it is intended that the claimed subject matter be viewed broadly, and be defined only as set forth in the accompanying claims.